import math

def filtre(P, a, b):
    s = []
    for p in P:
	if len(p) >= a and len(p) <= b:
	    s.append(p)

    return s

def permutation(k, L):
    pL = list(L)
    fact = 1
    i = 2
    while i < len(L) + 1:
	fact = fact * (i-1)
	pos = i - ((k/fact) % i) - 1
	swap = pL[pos]
	pL[pos] = pL[i-1]
	pL[i-1] = swap
	i += 1
    return pL

def permutations(L):
    p = []
    n = math.factorial(len(L))
    i = 0
    while i < n:
	p.append(permutation(i, L))
	i += 1
    return p

def permut3(L):
    p = []
    p.append(L[2])
    p.append(L[0])
    p.append(L[1])
    return p

def permuts3(L):
    P = []
    P.append(L)
    a = permut3(L)
    P.append(a)
    b = permut3(a)
    P.append(b)
    return P

def Cnp(L, n,p, l=None, res=None):
    """ Created: 2005.11.05 - Updated:
        Calcul du Cnp - ne pas renseigne l et res lors de l'appel """
    if l is None: l=[]
    if res is None: res=[]
    if p==0:
        res.append(l)
        return 
    if n==0: return  
    l1=list(l)
    l1.append(L[n-1])
    Cnp(L, n-1, p-1, l1, res)
    Cnp(L, n-1, p, l, res)
    return res

def cycles(Combis):
    Cycles = []
    for combi in Combis:
	if len(combi) == 3:
	    cycle = combi
	    Cycles.append(cycle)
	elif len(combi) == 4:
	    for perm in permuts3(combi[1:]):
		cycle = []
		cycle.append(combi[0])
		cycle.extend(perm)
		Cycles.append(cycle)
	else:
	    for c in Cnp(combi[1:], len(combi[1:]), len(combi) - 4):
		for p in permutations(c):
	    	    cycle = []
	    	    cycle.append(combi[0])
		    cycle.extend(p)
		    circ = []
		    for i in combi[1:]:
			if not i in c:
			    circ.append(i)
		    for pp in permuts3(circ):
			cycle2 = list(cycle)
			cycle2.extend(pp)
			Cycles.append(cycle2)

    return Cycles

def combi(n, a, b):
    C = []
    i = 0
    for i in range(a, b+1):
	for c in Cnp(range(n), n, i):
	    C.append(c)
    return C

def enumerer_cycles(n):
    return cycles(combi(n, 4, 7))
